//
// Created by DengLibin on 2019/1/9 0009.
//
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include<algorithm>
using namespace std;
/**
 * 整数反转
 */

int reverseInt(int num){

    int rev = 0;
    while(num != 0){
        int i = num % 10;
        num /= 10;
        if(rev > INT_MAX / 10 || (rev == INT_MAX/10 && i > 7)) return 0;//越界
        if(rev < INT_MIN / 10 || (rev == INT_MIN/10 && i < -8)) return 0;//越界
        rev = rev * 10 + i;
    }
    return  rev;
}

bool  contains(vector<int> v, vector<int> sub){
    set<int>s;
    for(int i = 0; i <sub.size(); i++){
        A:
        for(int j = 0;j < v.size();j++){
                if(sub[i] == v[j] && s.find(j)==s.end()){
                        s.insert(j);
                    goto A;
                }

        }
    }
    return s.size() == sub.size();
}
//是否包含

bool contains(vector<vector<int>> &v, vector<int> &subv){

    for(vector<int> v1 : v){
        if(contains(v1,subv)){
            return true;
        }
    }
    return false;
}



/**
 * 三数之和 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

    注意：答案中不可以包含重复的三元组。
 * @return
 */
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int >> rev;
    if(nums.size()<3){
        return rev;
    }
    sort(nums.begin(), nums.end());
    set<string> set;
    for(int i = 0; i < nums.size() - 2; i++){
        if(nums[i]>0){
            break;
        }
        for(int j = i+1; j < nums.size() -1; j++){
            if(nums[i] + nums[j]>0){
                break;
            }
            for(int k = j+1; k < nums.size(); k++){
                if(nums[i] + nums[j]+nums[k]>0){
                    break;
                }
                if(nums[i] + nums[j] + nums[k] == 0){
                    vector<int > v;
                    v.push_back(nums[i]);
                    v.push_back(nums[j]);
                    v.push_back(nums[k]);

                    if(!contains(rev, v) ){
                        rev.push_back(v);
                    }
                }
            }
        }
    }
    return rev;
}

void showV(vector<vector<int >> & v){
    for(vector<int >  v1 : v){
        for(int i : v1){
            cout << i<<",";
        }
        cout <<endl;
    }
}

int main51(){

    vector<int > v;
    v.push_back(-4);
    v.push_back(-2);
    v.push_back(1);
    v.push_back(-5);
    v.push_back(-4);
    v.push_back(-4);
    v.push_back(4);
    v.push_back(-2);
    v.push_back(0);//8
    v.push_back(4);
    v.push_back(0);//10
    v.push_back(-2);
    v.push_back(3);
    v.push_back(1);
    v.push_back(-5);
    v.push_back(0);//15
    vector<vector<int>> rev = threeSum(v);
    showV(rev);
    return 0;
}

